#ifndef _HY_TIMER_QUEUE_H_
#define _HY_TIMER_QUEUE_H_

//#include "zr_noncopyable.h"
#include <boost/date_time.hpp>

#if defined(_WIN32)
#include <hash_map>
using namespace stdext;
#else
#include <ext/hash_map>
using __gnu_cxx::hash_map; 
namespace __gnu_cxx
{
	template<> struct hash< void* >
	{
		size_t operator()(  void* const & x ) const
		{
			return hash< int >()( (int)x );
		}
	};
}

#endif


namespace hy {

	class timer_queue_base
		//: private zr_noncopyable
	{
	public:
		// Destructor.
		virtual ~timer_queue_base() {}

		// Whether there are no timers in the queue.
		virtual bool empty() const = 0;

		// Get the time to wait until the next timer.
		virtual boost::posix_time::time_duration wait_duration() const = 0;

		// Dispatch all ready timers.
		virtual void dispatch_timers() = 0;

		// Dispatch any pending cancels for timers.
		virtual void dispatch_cancellations() = 0;

		// Complete all timers that are waiting to be completed.
		virtual void complete_timers() = 0;

		// Destroy all timers.
		virtual void destroy_timers() = 0;
	};



	template <typename Time_Traits>
	class timer_queue
		: public timer_queue_base
	{
	public:
		// The time type.
		typedef typename Time_Traits::time_type time_type;

		// The duration type.
		typedef typename Time_Traits::duration_type duration_type;

		// Constructor.
		timer_queue()
			: timers_(),
			heap_(),
			cancelled_timers_(0),
			complete_timers_(0)
		{
		}

		// Add a new timer to the queue. Returns true if this is the timer that is
		// earliest in the queue, in which case the reactor's event demultiplexing
		// function call may need to be interrupted and restarted.
		template <typename Handler>
		bool enqueue_timer(const time_type& time, Handler handler, void* token)
		{
			// Ensure that there is space for the timer in the heap. We reserve here so
			// that the push_back below will not throw due to a reallocation failure.
			heap_.reserve(heap_.size() + 1);

			// Create a new timer object.
			std::auto_ptr<timer<Handler> > new_timer(
				new timer<Handler>(time, handler, token));

			// Insert the new timer into the hash.
			typedef typename hash_map<void*, timer_base*>::iterator iterator;
			typedef typename hash_map<void*, timer_base*>::value_type value_type;
			std::pair<iterator, bool> result =
				timers_.insert(value_type(token, new_timer.get()));
			if (!result.second)
			{
				result.first->second->prev_ = new_timer.get();
				new_timer->next_ = result.first->second;
				result.first->second = new_timer.get();
			}

			// Put the timer at the correct position in the heap.
			new_timer->heap_index_ = heap_.size();
			heap_.push_back(new_timer.get());
			up_heap(heap_.size() - 1);
			bool is_first = (heap_[0] == new_timer.get());

			// Ownership of the timer is transferred to the timer queue.
			new_timer.release();

			return is_first;
		}

		// Whether there are no timers in the queue.
		virtual bool empty() const
		{
			return heap_.empty();
		}

		// Get the time for the timer that is earliest in the queue.
		virtual boost::posix_time::time_duration wait_duration() const
		{
			if (heap_.empty())
				return boost::posix_time::pos_infin;
			return Time_Traits::to_posix_duration(
				Time_Traits::subtract(heap_[0]->time_, Time_Traits::now()));
		}

		// Dispatch the timers that are earlier than the specified time.
		virtual void dispatch_timers()
		{
			const time_type now = Time_Traits::now();
			while (!heap_.empty() && !Time_Traits::less_than(now, heap_[0]->time_))
			{
				timer_base* t = heap_[0];
				remove_timer(t);
				t->result_ = ZR_SUCCESS;
				t->prev_ = 0;
				t->next_ = complete_timers_;
				complete_timers_ = t;
			}
		}

		// Cancel the timers with the given token. Any timers pending for the token
		// will be notified that they have been cancelled next time
		// dispatch_cancellations is called. Returns the number of timers that were
		// cancelled.
		std::size_t cancel_timer(void* timer_token)
		{
			std::size_t num_cancelled = 0;
			typedef typename hash_map<void*, timer_base*>::iterator iterator;
			iterator it = timers_.find(timer_token);
			if (it != timers_.end())
			{
				timer_base* t = it->second;
				while (t)
				{
					timer_base* next = t->next_;
					remove_timer(t);
					t->prev_ = 0;
					t->next_ = cancelled_timers_;
					cancelled_timers_ = t;
					t = next;
					++num_cancelled;
				}
			}
			return num_cancelled;
		}

		// Dispatch any pending cancels for timers.
		virtual void dispatch_cancellations()
		{
			while (cancelled_timers_)
			{
				timer_base* this_timer = cancelled_timers_;
				this_timer->result_ = ZR_E_OPERATION_ABORTED;
				cancelled_timers_ = this_timer->next_;
				this_timer->next_ = complete_timers_;
				complete_timers_ = this_timer;
			}
		}

		// Complete any timers that are waiting to be completed.
		virtual void complete_timers()
		{
			while (complete_timers_)
			{
				timer_base* this_timer = complete_timers_;
				complete_timers_ = this_timer->next_;
				this_timer->next_ = 0;
				this_timer->complete();
			}
		}

		// Destroy all timers.
		virtual void destroy_timers()
		{
			typename hash_map<void*, timer_base*>::iterator i = timers_.begin();
			typename hash_map<void*, timer_base*>::iterator end = timers_.end();
			while (i != end)
			{
				timer_base* t = i->second;
				typename hash_map<void*, timer_base*>::iterator old_i = i++;
				timers_.erase(old_i);
				destroy_timer_list(t);
			}
			heap_.clear();
			timers_.clear();
			destroy_timer_list(cancelled_timers_);
			destroy_timer_list(complete_timers_);
		}

	private:
		// Base class for timer operations. Function pointers are used instead of
		// virtual functions to avoid the associated overhead.
		class timer_base
		{
		public:
			// Delete the timer and post the handler.
			void complete()
			{
				complete_func_(this, result_);
			}

			// Delete the timer.
			void destroy()
			{
				destroy_func_(this);
			}

		protected:
			typedef void (*complete_func_type)(timer_base*,
				const hy_err_t&);
			typedef void (*destroy_func_type)(timer_base*);

			// Constructor.
			timer_base(complete_func_type complete_func, destroy_func_type destroy_func,
				const time_type& time, void* token)
				: complete_func_(complete_func),
				destroy_func_(destroy_func),
				time_(time),
				token_(token),
				next_(0),
				prev_(0),
				heap_index_(
				std::numeric_limits<size_t>::max BOOST_PREVENT_MACRO_SUBSTITUTION())
			{
			}

			// Prevent deletion through this type.
			~timer_base()
			{
			}

		private:
			friend class timer_queue<Time_Traits>;

			// The function to be called to delete the timer and post the handler.
			complete_func_type complete_func_;

			// The function to be called to delete the timer.
			destroy_func_type destroy_func_;

			// The result of the timer operation.
			hy_err_t result_;

			// The time when the timer should fire.
			time_type time_;

			// The token associated with the timer.
			void* token_;

			// The next timer known to the queue.
			timer_base* next_;

			// The previous timer known to the queue.
			timer_base* prev_;

			// The index of the timer in the heap.
			size_t heap_index_;
		};

		// Adaptor class template for using handlers in timers.
		template <typename Handler>
		class timer
			: public timer_base
		{
		public:
			// Constructor.
			timer(const time_type& time, Handler handler, void* token)
				: timer_base(&timer<Handler>::complete_handler,
				&timer<Handler>::destroy_handler, time, token),
				handler_(handler)
			{
			}

			// Delete the timer and post the handler.
			static void complete_handler(timer_base* base,
				const hy_err_t& result)
			{
				// Take ownership of the timer object.
				typedef timer<Handler> this_type;
				this_type* this_timer(static_cast<this_type*>(base));
				typedef handler_alloc_traits<Handler, this_type> alloc_traits;
				handler_ptr<alloc_traits> ptr(this_timer->handler_, this_timer);

				// Make a copy of the error_code and the handler so that the memory can
				// be deallocated before the upcall is made.
				hy_err_t ec(result);
				Handler handler(this_timer->handler_);

				// Free the memory associated with the handler.
				ptr.reset();

				// Make the upcall.
				handler(ec);
			}

			// Delete the timer.
			static void destroy_handler(timer_base* base)
			{
				// Take ownership of the timer object.
				typedef timer<Handler> this_type;
				this_type* this_timer(static_cast<this_type*>(base));
				typedef handler_alloc_traits<Handler, this_type> alloc_traits;
				handler_ptr<alloc_traits> ptr(this_timer->handler_, this_timer);

				// A sub-object of the handler may be the true owner of the memory
				// associated with the handler. Consequently, a local copy of the handler
				// is required to ensure that any owning sub-object remains valid until
				// after we have deallocated the memory here.
				Handler handler(this_timer->handler_);
				(void)handler;

				// Free the memory associated with the handler.
				ptr.reset();
			}

		private:
			Handler handler_;
		};

		// Move the item at the given index up the heap to its correct position.
		void up_heap(size_t index)
		{
			size_t parent = (index - 1) / 2;
			while (index > 0
				&& Time_Traits::less_than(heap_[index]->time_, heap_[parent]->time_))
			{
				swap_heap(index, parent);
				index = parent;
				parent = (index - 1) / 2;
			}
		}

		// Move the item at the given index down the heap to its correct position.
		void down_heap(size_t index)
		{
			size_t child = index * 2 + 1;
			while (child < heap_.size())
			{
				size_t min_child = (child + 1 == heap_.size()
					|| Time_Traits::less_than(
					heap_[child]->time_, heap_[child + 1]->time_))
					? child : child + 1;
				if (Time_Traits::less_than(heap_[index]->time_, heap_[min_child]->time_))
					break;
				swap_heap(index, min_child);
				index = min_child;
				child = index * 2 + 1;
			}
		}

		// Swap two entries in the heap.
		void swap_heap(size_t index1, size_t index2)
		{
			timer_base* tmp = heap_[index1];
			heap_[index1] = heap_[index2];
			heap_[index2] = tmp;
			heap_[index1]->heap_index_ = index1;
			heap_[index2]->heap_index_ = index2;
		}

		// Remove a timer from the heap and list of timers.
		void remove_timer(timer_base* t)
		{
			// Remove the timer from the heap.
			size_t index = t->heap_index_;
			if (!heap_.empty() && index < heap_.size())
			{
				if (index == heap_.size() - 1)
				{
					heap_.pop_back();
				}
				else
				{
					swap_heap(index, heap_.size() - 1);
					heap_.pop_back();
					size_t parent = (index - 1) / 2;
					if (index > 0 && Time_Traits::less_than(
						heap_[index]->time_, heap_[parent]->time_))
						up_heap(index);
					else
						down_heap(index);
				}
			}

			// Remove the timer from the hash.
			typedef typename hash_map<void*, timer_base*>::iterator iterator;
			iterator it = timers_.find(t->token_);
			if (it != timers_.end())
			{
				if (it->second == t)
					it->second = t->next_;
				if (t->prev_)
					t->prev_->next_ = t->next_;
				if (t->next_)
					t->next_->prev_ = t->prev_;
				if (it->second == 0)
					timers_.erase(it);
			}
		}

		// Destroy all timers in a linked list.
		void destroy_timer_list(timer_base*& t)
		{
			while (t)
			{
				timer_base* next = t->next_;
				t->next_ = 0;
				t->destroy();
				t = next;
			}
		}

		// A hash of timer token to linked lists of timers.
		hash_map<void*, timer_base*> timers_;

		// The heap of timers, with the earliest timer at the front.
		std::vector<timer_base*> heap_;

		// The list of timers to be cancelled.
		timer_base* cancelled_timers_;

		// The list of timers waiting to be completed.
		timer_base* complete_timers_;
	};



} // namespace zr


#endif //_HY_TIMER_QUEUE_H_
